|
David Bernard Shmoys (born 1959) is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems. In particular, his work has highlighted the role of linear programming in the design of approximation algorithms for NP-hard problems. He is known for his pioneering research on providing first constant factor performance guarantee for several scheduling and clustering problems including the k-center and k-median problems and the generalized assignment problem. Polynomial-time approximation schemes that he developed for scheduling problems have found applications in many subsequent works. His current research includes stochastic optimization, computational sustainability and optimization techniques in computational biology. Shmoys is married to Éva Tardos, who is a Jacob Gould Schurman Professor of Computer Science at Cornell University. ==Key contributions== Two of his key contributions are # Constant factor approximation algorithm for the Generalized Assignment Problem and Unrelated Parallel Machine Scheduling. # Constant factor approximation algorithm for k-Medians and Facility location problem. These contributions are described briefly below: 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「David Shmoys」の詳細全文を読む スポンサード リンク
|